package ecc;

/*
 * Elliptic curve signature engine.
 *
 * ================================
 *
 * ECDSA signature scheme.
 *
 * Notation:
 *
 * G: base point on the curve.
 * n: prime order of the base point
 * m: message representative (0 <= m < n)
 * x: private key (1 <= x < n)
 * Y: public key (Y = x*G)
 *
 * Signature generation:
 *
 * k = random()                         (condition: 1 <= k < n)
 * W = k*G
 * t = abscissa(W) mod n
 * r = t                                (condition: r != 0)
 * s = k^(-1)*(m + r*x) mod n           (condition: s != 0)
 *
 * The signature is the pair (r, s).
 *
 * Signature verification:
 *
 * z = s^(-1) mod n                     (condition: 1 <= s < n)
 * u = z*m mod n
 * v = z*r mod n                        (condition: 1 <= r < n)
 * W = u*G + v*Y = s^(-1)*(m + r*x)*G = k*G
 * t = abscissa(W) mod n
 *
 * The signature is accepted <=> t = r.
 *
 * ================================
 *
 * Nyberg-Rueppel signature scheme.
 *
 * Notation:
 *
 * G: base point on the curve.
 * n: prime order of the base point
 * m: message representative (0 <= m < n)
 * x: private key (1 <= x < n)
 * Y: public key (Y = x*G)
 *
 * Signature generation:
 *
 * k = random()                         (condition: 1 <= k < n)
 * W = k*G
 * t = abscissa(W) mod n
 * r = (m + t) mod n                    (condition: r != 0)
 * s = (k - r*x) mod n
 *
 * The signature is the pair (r, s).
 *
 * Signature verification:
 *
 * W = s*G + r*Y = (s + r*x)*G = k*G    (condition: 1 <= r < n, 0 <= s < n)
 * t = abscissa(W) mod n
 * z = (r - t) mod n
 *
 * The signature is accepted <=> z = m.
 *
 * ================================
 *
 * @author  Paulo S. L. M. Barreto
 */

import java.math.BigInteger;
import java.security.SecureRandom;
import java.security.MessageDigest;
import java.util.Arrays;

public class ESigns {

    public static final int ECDSA   = 0;
    public static final int ECNR    = 1;

    protected int alg = -1;
    protected MessageDigest md = null;

    private ECurve E = null;
    private BigInteger k = null;    // private random nonce (public random nonce: W = k*G)
    private BigInteger t = null;    // x-coordinate of W (mod n)
    private BigInteger r = null;    // first half of signature
    private BigInteger s = null;    // second half of signature
    private EPoint Y = null;

    public ESigns() {
    }

    /**
     * Create an elliptic key pair.
     *
     * @param    E      the elliptic curve containing the public key.
     * @param    prng   a cryptographically strong pseudo-random number generator.
     *
     * @return the generated key pair (BigInteger x, EPoint Y),
     * where x is the private key (0 < x < E.n) and Y is the normalized public key.
     */
    public static Object[] makeKeyPair(ECurve E, SecureRandom prng) {
        BigInteger x;
        // generate suitable private key x:
        int t = E.n.bitLength();
        do {
            x = new BigInteger(t, prng);
            if (x.compareTo(E.n) >= 0) {
                x = x.subtract(E.n);
            }
            /* invariant: 0 <= x < n */
        } while (x.signum() == 0);
        /* invariant: 0 < x < n */
        // compute the corresponding public key:
        EPoint Y = E.kG(x).normalize();
        return new Object[] {x, Y};
    }

    /**
     * Initialize signature generation with a given signature algorithm
     * over a given elliptic curve, given a suitable hash function and a prng.
     *
     * @param   alg     signature algorithm.
     * @param   E       elliptic curve.
     * @param   md      hash function.
     * @param   prng    pseudo-random number generator.
     *
     * @return  the signature nonce as a byte array.
     */
    byte[] init(int alg, ECurve E, MessageDigest md, SecureRandom prng) {
        if (alg != ECDSA && alg != ECNR) {
            throw new RuntimeException("invalid signature algorithm");
        }
        this.alg = alg;
        this.E = E;
        this.md = md;
        // choose random nonce (volatile key pair)
        do {
            Object[] pair = makeKeyPair(E, prng);
            k = (BigInteger)pair[0];
            EPoint W = (EPoint)pair[1];
            t = W.x.mod(E.n);
        } while (t.signum() == 0);
        int len = (E.n.bitLength() + 7)/8;
        byte[] n = new byte[len];
        byte[] h = t.toByteArray();
        if (h.length <= len) {
            Arrays.fill(n, 0, len - h.length, (byte)0);
            System.arraycopy(h, 0, n, len - h.length, h.length);
        } else {
            /*
             * this can only happen if the first octet is negative
             * (meaning a negative BigInteger in two's complement),
             * in which case a zero octet is prepended to the byte array h:
             */
            assert (h.length == len + 1 && h[0] == 0);
            System.arraycopy(h, 1, n, 0, len);
        }
        return n;
    }

    void update(byte[] msg, int off, int len) {
        if (len > 0) {
            md.update(msg, off, len);
        }
    }

    /**
     * Complete the signature computation for curve E using private key x.
     */
    byte[] sign(BigInteger x) {
        return sign(x, md.digest());
    }

    /**
     * Complete the signature computation for curve E using private key x and message digest d.
     *
     * @param   x   private key.
     * @param   d   message digest.
     *
     * @return  the signature as a byte array.
     */
    byte[] sign(BigInteger x, byte[] d) {
        int len = (E.n.bitLength() + 7)/8;
        byte[] sig = new byte[2*len];
        // compute message representative (0 <= m < E.n):
        byte[] h = new byte[1 + d.length];
        h[0] = 0; // this is necessary to ensure m >= 0
        System.arraycopy(d, 0, h, 1, d.length);
        BigInteger m = new BigInteger(h).mod(E.n);
        switch (alg) {
        case ECDSA:
            /*
             * ECDSA signature generation:
             *
             * k = random()                         (condition: 1 <= k < n)
             * W = k*G
             * t = abscissa(W) mod n
             * r = t                                (condition: r != 0)
             * s = k^(-1)*(m + r*x) mod n           (condition: s != 0)
             *
             * The signature is the pair (r, s).
             */
            // compute 1st signature component r:
            r = t;
            // compute 2nd signature component s:
            s = m.add(r.multiply(x)).mod(E.n);
            if (s.signum() == 0) {
                /*
                 * the probability of this event is exceedingly small,
                 * but if it does ever happen, a new nonce must be generated
                 * and the whole signing process started over again.
                 */
                throw new RuntimeException("invalid nonce");
            }
            s = s.multiply(k.modInverse(E.n)).mod(E.n);
            break;
        case ECNR:
            /*
             * Nyberg-Rueppel signature generation:
             *
             * k = random()                         (condition: 1 <= k < n)
             * W = k*G
             * t = abscissa(W) mod n
             * r = (m + t) mod n                    (condition: r != 0)
             * s = (k - r*x) mod n
             *
             * The signature is the pair (r, s).
             */
            // compute 1st signature component r:
            r = m.add(t).mod(E.n);
            if (r.signum() == 0) {
                /*
                 * the probability of this event is exceedingly small,
                 * but if it does ever happen, a new nonce must be generated
                 * and the whole signing process started over again.
                 */
                throw new RuntimeException("invalid nonce");
            }
            // compute 2nd signature component s:
            s = k.subtract(r.multiply(x)).mod(E.n);
            if (s.signum() == 0) {
                /*
                 * the probability of this event is exceedingly small,
                 * but if it does ever happen, a new nonce must be generated
                 * and the whole signing process started over again.
                 */
                throw new RuntimeException("invalid nonce");
            }
            break;
        default:
            throw new RuntimeException("engine not initialized");
        }
        // format signature (r, s):
        h = r.toByteArray();
        if (h.length <= len) {
            Arrays.fill(sig, 0, len - h.length, (byte)0);
            System.arraycopy(h, 0, sig, len - h.length, h.length);
        } else {
            /*
             * this can only happen if the first octet is negative
             * (meaning a negative BigInteger in two's complement),
             * in which case a zero octet is prepended to the byte array:
             */
            assert (h.length == len + 1 && h[0] == 0);
            System.arraycopy(h, 1, sig, 0, len);
        }
        h = s.toByteArray();
        if (h.length <= len) {
            Arrays.fill(sig, len, 2*len - h.length, (byte)0);
            System.arraycopy(h, 0, sig, 2*len - h.length, h.length);
        } else {
            /*
             * this can only happen if the first octet is negative
             * (meaning a negative BigInteger in two's complement),
             * in which case a zero octet is prepended to the byte array:
             */
            assert (h.length == len + 1 && h[0] == 0);
            System.arraycopy(h, 1, sig, len, len);
        }
        alg = -1;
        return sig;
    }

    /**
     * Initialize signature verification with a given signature algorithm
     * over a given elliptic curve, given a suitable hash function,
     * the public key and the purported signature.
     *
     * @param   alg     signature algorithm.
     * @param   E       elliptic curve.
     * @param   md      hash function.
     *
     * @return  signature nonce as a byte array.
     */
    byte[] init(int alg, ECurve E, MessageDigest md, EPoint Y, byte[] sig, int pos) {
        if (alg != ECDSA && alg != ECNR) {
            throw new RuntimeException("invalid signature algorithm");
        }
        this.alg = alg;
        this.E = E;
        this.md = md;
        int len = (E.n.bitLength() + 7)/8;
        byte[] n = new byte[len];
        boolean ret = false;

        this.Y = Y;
        // parse signature:
        byte[] h = new byte[1 + len];
        h[0] = 0;
        System.arraycopy(sig, pos, h, 1, len);
        r = new BigInteger(h);
        System.arraycopy(sig, pos + len, h, 1, len);
        s = new BigInteger(h);
        switch (alg) {
        case ECDSA:
            if (r.signum() <= 0 || r.compareTo(E.n) >= 0) {
                throw new RuntimeException("Invalid signature component r");
            }
            if (s.signum() <= 0 || s.compareTo(E.n) >= 0) {
                throw new RuntimeException("Invalid signature component s");
            }
            t = r;
            System.arraycopy(sig, pos, n, 0, len);
            break;
        case ECNR:
            /*
             * W = s*G + r*Y = (s + r*x)*G = k*G    (condition: 1 <= r < n, 0 <= s < n)
             * t = abscissa(W) mod n
             */
            if (r.signum() <= 0 || r.compareTo(E.n) >= 0) {
                throw new RuntimeException("Invalid signature component r");
            }
            if (s.signum() <  0 || s.compareTo(E.n) >= 0) {
                throw new RuntimeException("Invalid signature component s");
            }
            // compute double exponential:
            EPoint W = E.G.simultaneous(s, r, Y);
            t = W.x.mod(E.n);
            h = t.toByteArray();
            if (h.length <= len) {
                Arrays.fill(n, 0, len - h.length, (byte)0);
                System.arraycopy(h, 0, n, len - h.length, h.length);
            } else {
                /*
                 * this can only happen if the first octet is negative
                 * (meaning a negative BigInteger in two's complement),
                 * in which case a zero octet is prepended to the byte array h:
                 */
                assert (h.length == len + 1 && h[0] == 0);
                System.arraycopy(h, 1, n, 0, len);
            }
            break;
        default:
            throw new RuntimeException("engine not initialized");
        }
        return n;
    }

    /**
     * Verify a signature.
     *
     * @return    true if the signature is valid, otherwise false.
     */
    boolean verify() {
        return verify(md.digest());
    }

    /**
     * Verify a signature.
     *
     * @return    true if the signature is valid, otherwise false.
     */
    boolean verify(byte[] d) {
        if (alg != ECDSA && alg != ECNR) {
            throw new RuntimeException("engine not initialized");
        }
        int len = (E.n.bitLength() + 7)/8;
        boolean ret = false;
        EPoint W;
        BigInteger u, v, z;

        // compute message representative (0 <= m < E.n):
        byte[] h = new byte[1 + d.length];
        h[0] = 0; // this is necessary to ensure m >= 0
        System.arraycopy(d, 0, h, 1, d.length);
        BigInteger m = new BigInteger(h).mod(E.n);
        switch (alg) {
        case ECDSA:
            /*
             * ECDSA signature verification:
             *
             * z = s^(-1) mod n                     (condition: 1 <= s < n)
             * u = z*m mod n
             * v = z*r mod n                        (condition: 1 <= r < n)
             * W = u*G + v*Y = s^(-1)*(m + r*x)*G = k*G
             * t = abscissa(W) mod n
             *
             * The signature is accepted <=> t = r.
             */
            // compute s^(-1) mod n:
            z = s.modInverse(E.n);
            // compute double exponential:
            u = z.multiply(m).mod(E.n);
            v = z.multiply(r).mod(E.n);
            W = E.G.simultaneous(u, v, Y);
            t = W.x.mod(E.n);
            // complete verification:
            ret = (t.compareTo(r) == 0);
            break;
        case ECNR:
            /*
             * Nyberg-Rueppel signature verification:
             *
             * W = s*G + r*Y = (s + r*x)*G = k*G    (condition: 1 <= r < n, 0 <= s < n)
             * t = abscissa(W) mod n
             * z = (r - t) mod n
             *
             * The signature is accepted <=> z = m.
             */
            z = r.subtract(t).mod(E.n);
            // complete verification:
            ret = (z.compareTo(m) == 0);
            break;
        default:
            throw new RuntimeException("engine not initialized");
        }
        alg = -1;
        return ret;
    }

}
